package com.cloud.code.算法.斐波拉契数列;

public class Demo {

    /**
     * 斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……
     * <p>
     * 特别指出：第0项是0，第1项是第一个1。
     * <p>
     * 这个数列从第三项开始，每一项都等于前两项之和。
     *
     * @param args
     */
    public static void main(String[] args) {

        long number = 1000;
//
//        long fibonacci = fibonacci(number);
//        System.out.println(fibonacci);

        long res = getRes(number);
        System.out.println(res);
    }

    /**
     * 递归的方法时间复杂度随着n的增加 2^n
     *
     * @param number
     * @return
     */
    public static long fibonacci(long number) {
        if ((number == 0) || (number == 1))
            return number;
        else
            return fibonacci(number - 1) + fibonacci(number - 2);
    }

    public static long getRes(long number) {

        long a = 0;
        long b = 1;
        long count = 0;
        long ret = 0;
        while (count < number-1){
            ret = a + b;
            a = b;
            b = ret;
            count ++;
        }
        return ret;

    }

}
